// POJ 3070

#include <iostream>
#include <algorithm>
using namespace std;

#define MOD 10000

struct Vector
{
	enum
	{
		ROW = 2,
		COL = 2
	};

	Vector() {}

	Vector operator*(const Vector &other)
	{
		Vector res;
		for (int i = 0; i < ROW; ++i)
			for (int j = 0; j < COL; ++j)
			{
				int tmp = 0;
				for (int k = 0; k < COL; ++k)
					tmp += v[i][k] * other.v[k][j];
				res.v[i][j] = tmp % MOD;
			}
		return res;
	}

	Vector pow(int p)
	{
		if (p == 1)
			return *this;

		if ((p & 1) == 1)
		{
			Vector tmp = pow((p - 1) / 2);
			return tmp * tmp * (*this);
		}
		else
		{
			Vector tmp = pow(p / 2);
			return tmp * tmp;
		}
	}
	
	int v[ROW][COL];
};

int main()
{
	Vector vt;
	vt.v[0][0] = vt.v[0][1] = vt.v[1][0] = 1;
	vt.v[1][1] = 0;
	int n;
	while (scanf("%d", &n) && n != -1)
	{
		int ans;
		if (n == 0)
			ans = 0;
		else if (n == 1)
			ans = 1;
		else
		{
			Vector res = vt.pow(n - 1);
			ans = res.v[0][0];
		}
		printf("%d\n", ans);
	}
	system("pause");
	return 0;
}